//在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 
//
// 示例 1: 
//
// 输入: [3,2,1,5,6,4] 和 k = 2
//输出: 5
// 
//
// 示例 2: 
//
// 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
//输出: 4 
//
// 说明: 
//
// 你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。 
// Related Topics 堆 分治算法 
// 👍 635 👎 0

package leetcode.editor.cn;

import javax.swing.plaf.metal.MetalTabbedPaneUI;
import java.util.PriorityQueue;

//Java：数组中的第K个最大元素
/*
* （1）使用小顶堆   时间复杂度 O(nlogn)
* （2）使用快排的partition函数  时间复杂度O(n)
* */
public class P215KthLargestElementInAnArray {
    public static void main(String[] args) {
        Solution solution = new P215KthLargestElementInAnArray().new Solution();
        // TO TEST
        int[] arr = {99,99};
        int res = solution.findKthLargest(arr, 1);
        // int res = solution.findKthSmaller(arr, 2);
        System.out.println(res);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /*
         * 使用小顶堆
         * 时间复杂度分析  遍历数组的每一个元素时间复杂度为n
         * 每次更新小顶堆的时间复杂度为 O(logn),因此更新n个元素的时间复杂度为O(nlogn)
         * 因此时间复杂度为O(nlogn)
         * */
        public int findKthLargest1(int[] nums, int k) {
            if (nums == null || k > nums.length) {
                return -1;
            }

            //jdk优先队列默认是小顶堆
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k);

            for (int e : nums) {
                if (priorityQueue.size() < k) {
                    priorityQueue.offer(e);
                } else {
                    if (e > priorityQueue.peek()) {
                        priorityQueue.poll();
                        priorityQueue.offer(e);
                    }
                }
            }

            return priorityQueue.peek();
        }

        /*
         * 拓展 找第k小元素
         * */

        public int findKthSmaller(int[] nums, int k) {
            if (nums == null || k > nums.length) {
                return -1;
            }

            //jdk优先队列默认是小顶堆  使用lambda表达式
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, (a, b) -> b - a);

            for (int e : nums) {
                if (priorityQueue.size() < k) {
                    priorityQueue.offer(e);
                } else {
                    if (e < priorityQueue.peek()) {
                        priorityQueue.poll();
                        priorityQueue.offer(e);
                    }
                }
            }

            return priorityQueue.peek();
        }

        /*
         * 使用快排的partition函数
         *
         * */
        public int findKthLargest(int[] nums, int k) {
            if (nums == null || k > nums.length) {
                return -1;
            }
            int len = nums.length;
            int begin = 0;
            int end = len - 1;
            int index = partition(nums, begin, end, len);
            k = len - k;
            while (index != k) {
                if (index < k) {
                    //起始坐标设置为index+1
                    index = partition(nums, index+1, end, len);
                } else {
                    //末尾坐标设置为index-1
                    index = partition(nums, begin, index-1, len);
                }
            }
            return nums[index];
        }

        public int partition(int[] nums, int begin, int end, int len) {
            //这里的边界条件 一定不要写成begin>=end会导致缺失一个数
            if (begin < 0 || begin > end || end < 0 || end >= len) {
                return -1;
            }

            int index = begin + (int) (Math.random() * (end - begin + 1));
            swap(nums, index, end);
            int small = begin - 1;
            for (int i = begin; i < end; i++) {
                if (nums[i] < nums[end]) {
                    small++;
                    if (small != i) {
                        swap(nums, small, i);
                    }
                }
            }

            small++;
            swap(nums, small, end);
            return small;
        }
        public void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }


//leetcode submit region end(Prohibit modification and deletion)

}
